'''
https://leetcode.cn/problems/as-far-from-land-as-possible/description/
'''
from collections import deque
from typing import List


class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append((i, j))
                    visited[i][j] = True
        distance = -1
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                    if 0 <= x < m and 0 <= y < n and not visited[x][y] and grid[x][y] == 0:
                        q.append((x, y))
                        visited[x][y] = True
            distance += 1
        return distance if distance else -1
